Reducing Tile Complexity for the Self-Assembly of Scaled Shapes Through Temperature Programming

摘要

This paper concerns the self-assembly of scaled-up versions of arbitraryfinite shapes. We work in the multiple temperature model that was introduced byAggarwal, Cheng, Goldwasser, Kao, and Schweller (Complexities for GeneralizedModels of Self-Assembly, SODA 2004). The multiple temperature model is anatural generalization of Winfree's abstract tile assembly model, where thetemperature of a tile system is allowed to be shifted up and down asself-assembly proceeds. We first exhibit two constant-size tile sets in whichscaled-up versions of arbitrary shapes self-assemble. Our first tile set hasthe property that each scaled shape self-assembles via an asymptotically"Kolmogorov-optimum" temperature sequence but the scaling factor grows with thesize of the shape being assembled. In contrast, our second tile set assembleseach scaled shape via a temperature sequence whose length is proportional tothe number of points in the shape but the scaling factor is a constantindependent of the shape being assembled. We then show that there is noconstant-size tile set that can uniquely assemble an arbitrary (non-scaled,connected) shape in the multiple temperature model, i.e., the scaling isnecessary for self-assembly. This answers an open question of Kao and Schweller(Reducing Tile Complexity for Self-Assembly Through Temperature Programming,SODA 2006), who asked whether such a tile set existed.